import java.util.Arrays;

/**
 * @author : zzr
 * @description :测试堆的创建
 * @date :
 */
public class TestHeap {

    private int[] elem;
    private int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }

    //堆的初始化
    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建堆的方法
     */
    public void createHeap() {
        // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，根结点向下调整
        //完全二叉树中，最后一个结点的索引是usedSize - 1，其父结点的索引为(usedSize - 1 - 1) / 2
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整的方法
     * @param parent 表示当前要进行向下调整的父结点的索引
     * @param usedSize 表示当前堆中的元素的数列 用于判断子结点是否越界
     */
    private void shiftDown(int parent, int usedSize) {
        //左孩子下标
        int child = (2 * parent) + 1;

        while(child < usedSize) { //确保左孩子不越界

            //child + 1 < usedSize 用来检查右孩子是否存在
            //elem[child] < elem[child + 1] 判断左孩子的值是否小于右孩子
            if(child + 1 < usedSize && elem[child] < elem[child + 1]) {
                //如果有孩子存在，且右孩子的值大于左孩子，则将child指向右孩子
                //即child一定是 左右 孩子中值较大的下标
                child++;
            }
            //大根堆
            //进行交换
            if(elem[child] > elem[parent]) {

                swap(child, parent);

                //完成一次父节点和子节点的交换后，更新当前处理的节点位置，以便继续向下调整堆，
                parent = child;
                child = 2 * parent + 1; //再找到新的父结点的左孩子进行比较
            } else {
                //已经是 大根堆了
                break;
            }
        }
    }

    /**
     * 交换下标的方法
     * @param child
     * @param parent
     */
    private void swap(int child, int parent) {
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
    }


    /**
     * 堆中添加元素
     * @param val
     */
    public void offer(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        this.elem[usedSize] = val;
        //向上调整
        shiftUp(usedSize);
        usedSize++;
    }

    /**
     * 向上调整
     * @param child
     */
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            //大根堆
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    /**
     * 判断堆是否满
     * @return
     */
    private boolean isFull() {
        return elem.length == usedSize;
    }

    public int poll() {
        int ret = elem[0];
        swap(0,usedSize - 1);
        usedSize--;
        shiftDown(0,usedSize);
        return ret;
    }

    /**
     * 堆排序方法
     * 对原来的数据进行排序
     * 如果要求排的顺序是由小到大的，就建立一个大根堆，不断将大的根排序到后面
     * 如果要求排的顺序是由大到小的，就建立一个小根堆，不断将小的根排序到后面
     *
     */
    public void heapSort() {
        //end为最后最后一个元素的下标索引
        int end = usedSize - 1;

        while (end > 0) {
            swap(0,end);
            shiftDown(0,end);
            end--;
        }
    }
}
